package week6;

import java.util.Arrays;

/**
 *
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：12 ms, 在所有 Java 提交中击败了87.87% 的用户
 * 内存消耗：37.7 MB, 在所有 Java 提交中击败了79.67% 的用户
 * 通过测试用例：188 / 188
 * 炫耀一下:
 *
 *
 */
public class Week6CoinChange {

    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dynamicPlan = new int[max];
        Arrays.fill(dynamicPlan, max);
        dynamicPlan[0] = 0;
        for(int f1 = 1; f1 <= amount; f1++) {
            for(int f2 = 0; f2 < coins.length; f2++) {
                if(coins[f2] <= f1) {
                    dynamicPlan[f1] = Math.min(dynamicPlan[f1], dynamicPlan[f1 - coins[f2]] + 1);
                }
            }
        }

        int result = dynamicPlan[amount] > amount ? -1 : dynamicPlan[amount];
        return result;
    }
}
